Criticality in Sperner's Lemma

Sperner's Lemma is a result from combinatorial topology dating back to
1928 which provides, among other things, a combinatorial way of proving
Brouwer's fixed point theorem. In this talk, we answer a question posed
by Tibor Gallai in 1969 concerning criticality in Sperner's lemma,
listed as Problem 9.14 in the collection of Jensen and Toft [Graph
coloring problems, John Wiley & Sons, Inc., New York, 1995].

Sperner's lemma states that if a labelling of the vertices of a
triangulation of the d-simplex A with labels 1,2,...,d+1 has the
property that (i) each vertex of A receives a distinct label, and (ii)
any vertex lying in a face of A has the same label as one of the
vertices of that face, then there exists a rainbow facet (a facet whose
vertices have pairwise distinct labels). For d <= 2, it is not difficult
to show that for every facet F, there exists a labelling with the above
properties where F is the unique rainbow facet. For every d >= 3,
however, we construct an infinite family of examples where this is not
the case, which implies the answer to Gallai's question as a corollary.
The construction is based on the properties of a 4-polytope which had
been used earlier to disprove a claim of Theodore Motzkin on neighbourly
polytopes.

Joint work with Matej Stehlik and Riste Skrekovski.